package com.love.labuladong.twopoint.slidewindow;

/**
 * 134. 加油站
 */
public class OilPoint {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        // 车辆尝试从 0 ~ n-1 出发，看能不能走一圈
        // r : 窗口即将进来的数字的位置
        // len : 窗口的大小
        // sum : 窗口累加和
        for (int l = 0,r = 0,len = 0, sum =0 ; l < n; l++) {
            while (sum >= 0){
                // 当前窗口累加和 >= 0,尝试扩
                if(len == n){
                    return l;
                }
                // r : 窗口即将进来数字的位置
                r = (l + (len++)) % n;
                sum += gas[r] - cost[r];
            }
            // sum < 0, 此时 l 位置无法转一圈
            len--;
            sum -= gas[l] - cost[l];
        }



        return -1;
    }
}
